/**
 * @brief 树上差分抽象基类
 * @note 采用模板方法模式定义算法骨架
 */
class LCATree {
public:
    using i64 = long long;
protected:
    int n, root;
    std::vector<std::vector<int>> adj, parent;
    std::vector<int> depth;
    std::vector<i64> diff;
    
    static const int max_high = 20;

    void dfsLca(int u, int fa) {
        depth[u] = depth[fa] + 1;
        parent[u][0] = fa;
        for(int i = 1; i <= max_high; i++) {
            parent[u][i] = parent[parent[u][i - 1]][i - 1];
        }
        for(auto v : adj[u]) {
            if(v == fa) {
                continue;
            }
            dfsLca(v, u);
        }
    }

    int lca(int a, int b) const {
        if(depth[a] < depth[b]) {
            std::swap(a, b);
        }
        for(int i = max_high; i >= 0; i--) {
            if(depth[parent[a][i]] >= depth[b]) {
                a = parent[a][i];
            }
        }
        if(a == b) {
            return a;
        }
        for(int i = max_high; i >= 0; i--) {
            if(parent[a][i] != parent[b][i]) {
                a = parent[a][i];
                b = parent[b][i];
            }
        }
        return parent[a][0];
    }

public:
    explicit LCATree(int _n, int _root = 0) 
    : n(_n),
      root(_root)
    {
        adj.assign(n, {});
        parent.resize(n, std::vector<int>(max_high + 1, 0));
        depth.resize(n, 0);
        diff.resize(n, 0);
    }

    virtual ~LCATree() = default;

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    void prepareLca(int _root = 0) {
        this->root = _root;
        depth[this->root] = 0;
        dfsLca(root, root);
    }

    virtual void applyparentdate(int u, int v, i64 val) = 0;
    virtual void calculateResult() = 0;

    i64 getAns(int u) const {
        return diff[u];
    }
    
};